

class Solution1:
    def fourSum(self, nums, target):
        nums.sort()
        length = len(nums)
        if length < 4:
            return []
        result = set()
        for i1 in range(length - 3):
            num1 = nums[i1]
            if num1 + nums[length - 1] + nums[length - 2] + nums[length - 3] < target:
                continue
            elif num1 + nums[i1 + 1] + nums[i1 + 2] + nums[i1 + 3] > target:
                break
            for i2 in range(i1 + 1, length - 2):
                num2 = nums[i2]
                if num1 + num2 + nums[length - 1] + nums[length - 2] < target:
                    continue
                elif num1 + num2 + nums[i2 + 1] + nums[i2 + 2] > target:
                    break
                for i3 in range(i2 + 1, length - 1):
                    num3 = nums[i3]
                    if num1 + num2 + num3 + nums[length - 1] < target:
                        continue
                    elif num1 + num2 + num3 + nums[i3 + 1] > target:
                        break
                    for i4 in range(i3 + 1, length):
                        num4 = nums[i4]
                        theSum = num1 + num2 + num3 + num4
                        if theSum == target:
                            result.add((num1, num2, num3, num4))
        return list(result)


class Solution2:
    def fourSum(self, nums, target):
        nums.sort()
        length = len(nums)
        if length < 4:
            return []
        result = set()
        for i1 in range(length - 3):
            num1 = nums[i1]
            if num1 + nums[length - 1] + nums[length - 2] + nums[length - 3] < target:
                continue
            elif num1 + nums[i1 + 1] + nums[i1 + 2] + nums[i1 + 3] > target:
                break
            for i2 in range(i1 + 1, length - 2):
                num2 = nums[i2]
                if num1 + num2 + nums[length - 1] + nums[length - 2] < target:
                    continue
                elif num1 + num2 + nums[i2 + 1] + nums[i2 + 2] > target:
                    break
                low = i2 + 1
                high = length - 1
                while(low < high):
                    theSum = nums[low] + nums[high] + num1 + num2
                    if theSum == target:
                        result.add((nums[low], nums[high], num1, num2))
                        while low < high and nums[low] == nums[low + 1]:
                            low += 1
                        while low < high and nums[high] == nums[high - 1]:
                            high -= 1
                        low += 1
                        high -= 1
                    elif theSum < target:
                        low += 1
                    else:
                        high -= 1
                        
        return list(result)

# inspired by discussion
class Solution3:
    def fourSum(self, nums, target):
        dic = dict()
        numsLength = len(nums)
        for i in range(numsLength):
            num1 = nums[i]
            for j in range(i + 1, numsLength):
                num2 = nums[j]
                twoSum = num1 + num2
                if twoSum not in dic:
                    dic[twoSum] = []
                dic[twoSum].append((i, j))
        res = set()

        for aKey in dic.keys():
            anotherKey = target - aKey
            if anotherKey in dic:
                for (i, j) in dic[aKey]:
                    for (k, l) in dic[anotherKey]:
                        if i!=k and i!=l and j!=k and j!=l:
                            sortedArray = sorted([nums[i],nums[j],nums[k],nums[l]])
                            res.add(tuple(sortedArray))
        return list(res)


class Test: 
    def test(self, solution):
        expected = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
        result   = solution.fourSum([1, 0, -1, 0, -2, 2], 0)
        print(result)


Test().test(Solution1())
Test().test(Solution2())
